//题目:
// 给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。
// 同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
// 每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。
// 你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
// 请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
#include<iostream>
#include<queue>
#include<unordered_map>

using namespace std;
//代码:
class Solution 
{
    //方向矢量:上、下、左、右
    int arr_x[4]={-1,1,0,0},arr_y[4]={0,0,-1,1};
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) 
    {
        //题意转换：找到“起始点”到“边界上的空格子”的最短路径
        //从起始位置开始，“一步一步”的走每条相连的路，直到找到“出口”，记录此时行走的步数

        //1.创建一个队列，存放每条路径的“下一步”
        queue<pair<int,int>> q;
        q.push(make_pair(entrance[0],entrance[1]));//插入起始位置
        maze[entrance[0]][entrance[1]]='+';//解决“回头路”问题
        int ret=0;
        //2.开始一层一层的“走迷宫”
        while(!q.empty())
        {
            ret++;
            int size=q.size();
            //逐层走
            for(int k=0;k<size;k++)
            {
                pair<int,int> pir=q.front();
                q.pop();
                //找到与(pir.first,pir.second)相邻(上下左右)的出路，并将其放入队列
                for(int i=0;i<4;i++)
                {
                    int x=pir.first+arr_x[i],y=pir.second+arr_y[i];
                    if(x>=0 && x<maze.size() && y>=0 && y<maze[0].size() && maze[x][y]=='.')
                    {
                        //注意:这里就是走到头了
                        if(x==0 || y==0 || x==maze.size()-1 || y==maze[0].size()-1)return ret;
                        
                        q.push(make_pair(x,y));
                        maze[x][y]='+';//解决“回头路”问题
                    }
                }
            }
        }
        return -1;
    }
};